package com.guzhi04;

//希尔排序（插入排序的优化版，分成组把组进行插入排序）（插入排序是对单个数据进行插入，希尔排序是对一组数据进行插入）插组泡到

public class Shell {
    //构造函数（无参）
        public Shell() {
        }
    //成员方法
        //判断v是否大于w
        public static boolean greater(int v,int w){
            return v>w;
        }
        //交换数组中索引i和所有j的值
        public static void exch(int[]a,int i,int j){
            int temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
        //对数组内的元素进行排序
        public static void sort(int[]a){
            int h=1;//------------------------------------------------>都是Knuth（克怒嗯）增量序列是希尔排序中常用的一种（间隔序列）
            while(h<a.length/3){//------------------------------------>
                h=3*h+1;
            }
            while(h>0){
                //外层循环
                for(int i=h;i<a.length;i++){
                    //内层循环
                    for(int j=i;j>=h;j=j-h){
                        if(greater(a[j-h],a[j])){
                            exch(a,j,j-h);
                        }else{
                            break;
                        }
                    }
                }
                h=h/3;//------------------------------------------------>
            }
        }
}
